

#include <iostream>
#include <vector>
#include <climits>
#include <cstdlib>
using namespace std;

void Test1()
{
	int n = 3, m = 3;
	vector<vector<int>> vv{ {3, 2, 1}, {4, 5, 6}, {7, 8, 9} };

	vector<vector<int>> dp(n+1, vector<int>(m+1));

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + vv[i-1][j-1];
		}
	}
	for (int i = 0; i <= n; ++i)
	{
		for (int j = 0; j <= m; ++j)
		{
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
}

void Test2()
{
	vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	vector<int> dp(v.size());

	dp[0] = v[0];
	for (int i = 1, n = dp.size(); i < n; ++i)
	{
		dp[i] = dp[i - 1] + v[i];
	}
	for (const auto x : dp)
	{
		cout << x << " ";
	}
	cout << endl;
}

int solution3(int n, int m, vector<vector<int>> a)
{
	vector<vector<int>> dp(n + 1, vector<int>(m + 1));

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + a[i - 1][j - 1];
		}
	}

	int mindiff = INT_MAX;
	for (int i = 1; i < n; ++i)
	{
		int sum1 = dp[i][m];
		int sum2 = dp[n][m] - sum1;
		mindiff = min(mindiff, abs(sum1 - sum2));
	}

	for (int j = 1; j < m; ++j)
	{
		int sum1 = dp[n][j];
		int sum2 = dp[n][m] - sum1;
		mindiff = min(mindiff, abs(sum1 - sum2));
	}

	return mindiff;
}

void Test3() 
{
	cout << (solution3(2, 3, { {1, 1, 4}, {5, 1, 4} }) == 0) << endl;
	cout << (solution3(3, 3, { {3, 2, 1}, {4, 5, 6}, {7, 8, 9} }) == 3) << endl;
	cout << (solution3(2, 2, { {1, 2}, {3, 4} }) == 2) << endl;
}

vector<int> solution4(int N, vector<int> R)
{
	if (!N)
		return {};
	if (1 == N)
		return { (int)(R[0] + 0.5) };

	vector<int> dp(N);
	dp[0] = R[0];

	for (int i = 1; i < N; ++i)
	{
		dp[i] = dp[i - 1] + R[i];
	}
	for (int i = 0; i < N; ++i)
	{
		dp[i] = dp[i] / (i + 1.0) + 0.5;
	}

	return dp;
}

void Test4() 
{
	cout << (solution4(5, { 1, 2, 3, 4, 10 }) == vector<int>{1, 2, 2, 3, 4}) << endl;
	cout << (solution4(3, { 5, 10, 15 }) == vector<int>{5, 8, 10}) << endl;
}

int main()
{
	Test1();
	//Test2();
	//Test3();
	//Test4();

	return 0;
}